数据结构17：什么是递归

目录

一、什么是递归（Recursion）？

二、初始递归：数列求和问题

1、问题分析

2、代码实现

3、代码分析

4、递归程序如何被执行

三、递归三定律

递归是一种解决问题的方法，其主要思想在于：

递归问题的分解方式非常独特，其算法方面的明显特征就是：在算法流程中调用自身。递归为我们提供了一种对复杂问题的优雅解决方案，精妙的递归算法常会出奇简单，令人赞叹。

问题：给定一个列表，返回所有数的和。列表中数的个数不定，大家可能很容易的想到用一个循环和一个累加变量迭代的实现，如下代码：

这样的程序很简单，但是假如没有循环语句呢？既不用循环for，也不用while，还能对不确定长度的列表求和吗？

我们直到，列表求和实际上是由一次次的加法实现的，而加法只有两个操作数，这是确定的。

那是否可以想办法，将问题规模较大的列表求和，分解为规模较小而且固定的两个数求和呢？这样的话，同样是求和问题，但是规模发生了变化，符合递归解决问题的特征。

首先，我们换个方式来表示列表求和：全括号表达式：(1 + (3 + (5 + (7 + 9))))

上面的式子中，最内层的括号(7 + 9)，这是不需要循环的，可以直接计算，实际上整个求和的过程是这样的：

观察上面的过程所包含的重复模式，可以把求和问题归纳为：

数列的和 = “首个数” + “余下数列”的和

如果数列包含的数烧到只有一个的话，他就是这个数列的和了。

上面的程序中：

递归函数调用和返回过程的链条：方向相反

关于数列求和问题：

数列求和问题首先具备了基本结束条件，当列表长度为1的时候，直接输出所包含的唯一数。

数列求和问题中，递归算法就是改变列表的长度，并向长度为1的状态演进。

调用自身是递归算法中最难理解的部分，实际上可以理解为：问题分解为了规模更小的相同问题。